// @algorithm @lc id=200 lang=cpp 
// @title number-of-islands


// #define print(...)
// @test([["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]])=1
// @test([["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]])=3
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        print("\ngrid=\n", Mat(grid))
        int m = grid.size(), n = grid[0].size();
        int ans = 0, dir[][2] = {{0,1}, {1,0}, {0, -1}, {-1, 0}}, F='A';
        function<void(int,int)> dfs = [&](int i, int j){
            grid[i][j] = F;
            for(auto &[x, y] : dir)
                if(0<=i+x && i+x<m && 0<=j+y && j+y<n && grid[i+x][j+y]=='1')
                    dfs(i+x, j+y);
        };
        for(int i=0; i<m; i++)
            for(int j=0; j<n; j++){
                if(grid[i][j] != '1') continue;
                dfs(i,j);
                ++ans;
                print(++F, "\n", Mat(grid))
            }
        return ans;
    }
};